package sort;

import java.util.Arrays;

public class MergeSort_T {
    public static void main(String[] args) {
        int[] a = {1,6,1,2,3,3,6,6,8,9}; //{2,6,1,5,8,3,2,6,8,1};
        System.out.println(Arrays.toString(a));
        sort(a);
        System.out.println(Arrays.toString(a));
    }
    /*
        1.准备一个新的数组，和原数组长度相同
        2.处理的数据范围，最初从0到length-1 （left到right）
        3.计算中间位置：mid = (left+right)/2
        4.递归排序左侧，范围：left到mid
        5.递归排序右侧，范围：mid+1到right
        6.左右两侧数据，合并，放到新数组
        7.新数组中的数据，复制回到原数组

        最简问题： left >= right 重合或交叉，只有一个值，或没有值
     */
    private static void sort(int[] a) {
        int[] tmp = new int[a.length];
        sort(a, 0, a.length-1, tmp);
    }

    private static void sort(int[] a, int left, int right, int[] tmp) {
        if (left >= right) { //最简问题：重合或交叉，只有一个值，或没有值
            return;
        }
        int mid = (left+right)/2; // 计算中间位置
        sort(a, left, mid, tmp); //递归排序左侧
        sort(a, mid+1, right, tmp); //递归排序右侧
        merge(a, left, mid, right, tmp);  //把左侧排好序的数据，和右侧排好序的数据，进行合并
    }

    private static void merge(int[] a, int left, int mid, int right, int[] tmp) {
        int i=left; //用来访问数组左侧范围：left到mid
        int j=mid+1; //用来访问数组右侧范围：mid+1到right
        int k=left; //用来访问临时数组，范围：left到right
        while (i<=mid && j<=right) { //两侧都没有结束
            if (a[j] <= a[i]) { //原数组i和j位置比较大小，j位置的小值或相等值，放到临时数组的k位置
                tmp[k] = a[j];
                j++;
                k++;
            } else { // i位置的小值，放入临时数组的k位置
                tmp[k] = a[i];
                i++;
                k++;
            }
        }

        // 如果循环i没有结束
        if (i <= mid) {
            //把i到mid范围的数据，复制到临时数组的k位置
            System.arraycopy(a,i,tmp,k,mid-i+1); //原数组,原数组起始位置,目标数组,目标数组起始位置,数据的数量
            //while (i <= mid) {
            //    tmp[k] = a[i];
            //    i++;
            //    k++;
            //}
        } else {
            // 如果循环j没有结束
            // 把j到right范围的数据，复制到临时数组的k位置
            System.arraycopy(a, j, tmp, k, right-j+1);
        }
        // 从tmp数组，把left到right范围已经有序的数据，复制回到原数组
        System.arraycopy(tmp, left, a, left, right-left+1);
    }
}
